package com.sjf.day03.binarysorttree;

import cn.hutool.core.util.ObjectUtil;

/**
 * 二叉排序树
 *
 * @author <huangtang>
 * @since 2022/1/11 10:06
 **/
public class BinarySortTreeDemo {

    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }

        binarySortTree.midOrder();
        binarySortTree.delNode(1);
        binarySortTree.delNode(3);
        binarySortTree.delNode(5);
        binarySortTree.delNode(12);
        binarySortTree.delNode(9);
        binarySortTree.delNode(7);
        binarySortTree.delNode(10);

        System.out.println("删除节点后");
        binarySortTree.midOrder();
        System.out.println("root节点是："+binarySortTree.root);
    }

}


/**
 * 二叉排序树
 */
class BinarySortTree{
    Node root; //头节点

    /**
     * 删除节点
     * @param val 删除节点的val
     */
    public void delNode(int val){
        if(root == null){
            return;
        }else{
            //找到删除的节点
            Node targetNode = search(val);
            if(ObjectUtil.isNull(targetNode)){
                return;
            }

            if(ObjectUtil.isNull(root.left) && ObjectUtil.isNull(root.right)){
                //删除的树中只有一个节点
                root = null;
                return;
            }

            //去找到targetNode的父节点
            Node parent = searchParent(val);

            //删除的节点是叶子节点
            if(targetNode.left == null && targetNode.right == null ){
                if(parent.left!=null && parent.left.val == targetNode.val){
                    parent.left = null;
                }else if(parent.right!=null && parent.right.val == targetNode.val){
                    parent.right = null;
                }
            }else if(targetNode.left!=null && targetNode.right!=null){
                //删除有两颗子树的节点
                targetNode.val = delRightTreeMin(targetNode.right);
                //targetNode.val = delLeftTreeMax(targetNode.left);
            }else{
                //删除只有一棵子树的节点
                if(targetNode.left!=null){
                    if(parent == null){
                        root = root.left;
                        return;
                    }
                    //子树在左边
                    if(parent.left.val == val){
                        //如果targetNode是parent的左子节点
                        parent.left = targetNode.left;
                    }else{
                        //如果targetNode是parent的右子节点
                        parent.right = targetNode.left;
                    }
                }else{
                    if(parent == null){
                        root = root.right;
                        return;
                    }
                    //子树在右边
                    if(parent.right.val == val){
                        parent.right = targetNode.right;
                    }else{
                        parent.left = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 找到右子树的最小节点返回并删除
     * @param node 传入的节点为当前节点
     * @return 返回最小节点对应的val
     */
    public int delRightTreeMin(Node node){
        Node temp = node;
        //循环查找左节点，直到最小的找到
        while(temp.left != null){
            temp = temp.left;
        }
        delNode(temp.val); //删除最小节点
        return temp.val;
    }

    /**
     * 找到左子树的最大节点返回并删除
     * @param node 传入的节点为当前接地爱你
     * @return 返回最大节点对应的val
     */
    public int delLeftTreeMax(Node node){
        Node temp = node;
        while(temp.right!=null){
            temp = temp.right;
        }
        delNode(temp.val);
        return temp.val;

    }

    //查找要删除的节点
    public Node search(int val){
        if(root == null){
            return null;
        }else{
            return root.search(val);
        }
    }

    //查找父节点
    public Node searchParent(int val){
        if(root==null){
            return null;
        }else{
            return root.searchParent(val);
        }
    }


    /**
     * 添加节点
     * @param node
     */
    public void add(Node node){
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }

    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root == null){
            System.out.println("树为空，无法中序遍历");
        }else{
            root.midOrder();
        }
    }
}

/**
 * 创建树节点
 */
class Node{
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    /**
     *  查找要删除的节点
     * @param val 要删除节点的值
     * @return
     */
    public Node search(int val){
        if(this.val == val) {
            return this;
        }else if(val < this.val){
            //递归左子树
            if(this.left == null){
                return null;
            }
            return this.left.search(val);
        }else {
            //递归右子树
            if(this.right == null){
                return null;
            }
            return this.right.search(val);
        }
    }

    /**
     * 查找要删除节点的父节点
     * @param val 查找节点的值
     * @return 删除节点的父节点
     */
    public Node searchParent(int val){
        if((this.left!=null && this.left.val == val) || (this.right!=null && this.right.val == val)){
            return this;
        }else {
            //如果查找的值小于当前节点,并且当前节点的左子节点不为空
            if(val < this.val && this.left!=null){
                return this.left.searchParent(val); //递归左子树查找
            }else if(val >= this.val && this.right!=null){
                return this.right.searchParent(val); //递归右子树查找
            }else{
                return null;//没有父节点
            }
        }
    }

    /**
     * 添加节点
     * @param node 需要添加的节点
     */
    public void add(Node node){
        if(node == null ) return;

        if(node.val < this.val){
            if(this.left == null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }else if(node.val > this.val){
            if(this.right == null) {
                this.right = node;
            }else{
                this.right.add(node);
            }
        }else {
            if(this.right == null){
                this.right = node;
            }else{
                this.right.add(node);
            }
        }

    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(this.left!=null){
            this.left.midOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.midOrder();
        }
    }
}
